package cn.lbd.arithmetic.sort;

import org.junit.Test;

import java.util.Arrays;

public class QuickSort {
    public static int patition(int[] a,int s,int t){
        int i=s, j=t;
        int tmp = a[s];
        while(i!=j){
            while(j>i && a[j]>tmp){
                j--;
            }
            a[i]=a[j];
            while (j>i && a[i]<tmp){
                i++;
            }
            a[j]=a[i];
        }
        a[i]=tmp;
        return i;
    }

    public static void sort(int[] a,int s,int t){
        if(s < t){//每个子串长度为1时即0<-1,这就是递归出口
            int patition = patition(a, s, t);
            sort(a,s,patition-1);
            sort(a,patition+1,t);
        }
    }

    public static void main(String[] args) {
        int[] a = {177,3,253,14,11,9};
        int end=a.length-1;
        sort(a,0,end);
        System.out.println(Arrays.toString(a));
    }

    //80000数据   ？？？
    @Test
    public void batchTest(){
        int[] arr = new int[800];
        int length=arr.length-1;
        for(int i =0; i < 800;i++) {
            arr[i] = (int)(Math.random() * 8000000);
        }

        long start = System.currentTimeMillis();

        sort(arr,0,length);

        long end = System.currentTimeMillis();

        System.out.println((end-start));
    }
}
